package array;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/8/23 15:54
 * 数组习题：
 *
 * 众数问题：
 *          在一组数据中，找一个出现次数超过1/2的数，这个数最多只有一个
 *          在一组数据中，找一个出现次数超过1/3的数，这个数最多只有两个
 *          在一组数据中，找一个出现次数超过1/(n+1)的数，这个数最多只有n个
 *    解法一：排序法  O(nlogn)
 *    解法二：摩尔投票法 O(n)
 *              candidate 记录 候选人
 *              count记录票数
 */
public class ArrayHomeWork {
    public static void main(String[] args) {
//        int[] arr = {1,2,3,4,5,6,7,9,11,10};
//        changeSet(arr);
//        System.out.println(Arrays.toString(arr));
//        int[] arr={1,2,3,4,5,6,7,8,9,10};
//        System.out.println(binaryFind(arr,10));
//        int[] arr = {1,2,3,4,5,6,7,9,11,10,8};
//        int[] nums = {2,7,11,15};
//        int target = 9;
////        bubbleSort(arr);
//        System.out.println(Arrays.toString(twoNumSum( nums, 9)));
//        int[] arr = {1,2,3,1,2,3,4};
//        System.out.println(oneTime(arr));
//        int[] arr = {2,2,1,1,1,2,2};
//        System.out.println(mostNumVote(arr));
//        int[] arr ={1,2,34,3,4,5,7,23,12};
//        System.out.println(existThreeOdds(arr));
//        int[] arr={1,2,3};
//        transform(arr);
//        System.out.println(Arrays.toString(arr));

    }
    //1.调整数组顺序使得 奇数位于偶数之前。调整之后，不关心大小顺序。
    //如数组：[1,2,3,4,5,6]  调整后可能是：[1, 5, 3, 4, 2, 6]
    //一个left从左往右找偶数，一个right从右往左找奇数，找到就停在这个位置，进行交换。依次循环
    public static void changeSet(int[] arr){
        int left = 0;//找偶数
        int right = arr.length-1;//找奇数
        while(left<right){
            if((arr[left]%2==0)&&(arr[right]%2!=0)){
                int tem = arr[left];
                arr[left]=arr[right];
                arr[right]=tem;
            }
            if(arr[left]%2!=0){
                left++;
            }
            if (arr[right]%2==0){
                right--;
            }
        }
    }
//    public static void changeSet(int[] arr){
//        int left = 0;//找偶数
//        int right = arr.length-1;//找奇数
//        while(left<right){
//            while(left<right&&arr[left]%2!=0){
//                left++;
//            }
//            while(left<right&&arr[right]%2==0){
//                right--;
//            }
//            if((arr[left]%2==0)&&(arr[right]%2!=0)){
//                int tem = arr[left];
//                arr[left]=arr[right];
//                arr[right]=tem;
//            }
//
//        }
//    }
    //给定一个有序整型数组, 实现二分查找
    public static int binaryFind(int[] arr,int toFind){
        int left = 0;
        int right = arr.length-1;
        int mid;
        while(left<=right){
            mid = left+((right-left)>>1);
            if(arr[mid]==toFind){
                return mid;
            }else if(toFind>arr[mid]){
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return -1;
    }
    //2.给定一个整型数组, 实现冒泡排序(升序排序)
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            boolean flag =true;
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]){
                    flag=false;
                    int tem=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tem;
                }
            }
            if(flag==true){
                break;
            }
        }
    }
    //3.给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，
    //并返回它们的数组下标。
    //你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
    //你可以按任意顺序返回答案。
    //示例 1：
    //输入：nums = [2,7,11,15], target = 9
    //输出：[0,1]
    //解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
    public static int[] twoNumSum(int[] nums,int target){
        int[] ret=new int[2];
        outter:
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length-1; j >i; j--) {
                if ((nums[i] + nums[j] == target)){
                    ret[0]=i;
                    ret[1]=j;
                    break outter;
                }
            }
        }
        return ret;
    }

    //4.给你一个整数数组 arr，
    // 请你判断数组中是否存在连续三个元素都是奇数的情况：
    // 如果存在，请返回 true ；否则，返回 false 。
    public static boolean existThreeOdds(int[] arr){
        int count =0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]%2!=0){
                count++;
            }else {
                count=0;
            }
            if (count==3){
                return true;
            }
        }
        return false;
    }
    //5.给定一个大小为 n 的数组，找到其中的多数元素。
    // 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    //你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    //法一：排序法
    public static int mostNum(int[] arr){
        //bubbleSort(arr);
        Arrays.sort(arr);//工具类
        return arr[arr.length/2];
    }
    //法二：摩尔投票法
    public static int mostNumVote(int[] arr){
        int count =0;
        int candidate = -1;
        for (int i :arr) {
                if(count==0){
                    candidate=i;
                }
                if(candidate!=i){
                    //反对
                    count--;
                }else{
                    //赞同
                    count++;
                }
        }
        return candidate;
    }

    //7.实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 ,
    // 并设置到对应的数组元素上.
    // 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
    public static void transform(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            arr[i]*=2;
        }
    }
}
